Statistical relational models provide compact encodings of probabilistic dependencies in relational domains, but result in highly intractable graphical models. The goal of lifted inference is to carry out probabilistic inference without needing to reason about each individual separately, by instead treating exchangeable, undistinguished objects as a whole. In this paper, we study the domain recursion inference rule, which, despite its central role in early theoretical results on domain-lifted inference, has later been believed redundant. We show that this rule is more powerful than expected, and in fact significantly extends the range of models for which lifted inference runs in time polynomial in the number of individuals in the domain. This includes an open problem called S4, the symmetric transitivity model, and a first-order logic encoding of the birthday paradox. We further identify new classes S2FO2 and S2RU of domain-liftable theories, which respectively subsume FO2 and recursively unary theories, the largest classes of domain-liftable theories known so far, and show that using domain recursion can achieve exponential speedup even in theories that cannot fully be lifted with the existing set of inference rules.

This paper makes a concrete contribution to lifted probabilistic inference, showing that the domain recursion rule can be used to solve certain interesting problems that are intractable for state-of-the-art lifted inference software. The insights here seem likely to be incorporated into upcoming versions of those packages. However, some of the statements in the paper are not sufficiently precise. The description of the domain recursion rule itself (p. 5, top) is much less precise than the definition in the 2011 paper that introduced it. It's not clear what the preconditions are for applying the rule or exactly how it transforms the theory. Also, the description mentions caching (line 175), but it would be helpful to explain how the inference algorithm ends up making multiple calls to the cache.

Statistical relational models provide compact encodings of probabilistic dependencies in relational domains, but result in highly intractable graphical models. The goal of lifted inference is to carry out probabilistic inference without needing to reason about each individual separately, by instead treating exchangeable, undistinguished objects as a whole. In this paper, we study the domain recursion inference rule, which, despite its central role in early theoretical results on domain-lifted inference, has later been believed redundant. We show that this rule is more powerful than expected, and in fact significantly extends the range of models for which lifted inference runs in time polynomial in the number of individuals in the domain. This includes an open problem called S4, the symmetric transitivity model, and a first-order logic encoding of the birthday paradox.

Markov logic networks (MLNs) combine the power of first-order logic and probabilistic graphical models and as a result are ideally suited for solving large, complex problems in application domains that have both rich relational structure and large amount of uncertainty. However, inference in these rich, relational representations is quite challenging. The aim of this thesis is to advance the state-of-the-art in MLN inference, enabling it to solve much harder and more complex tasks than is possible today. To this end, I will develop techniques that exploit logical structures and symmetries that are either explicitly or implicitly encoded in the MLN representation and demonstrate their usefulness by using them to solve hard real-world problems in the field of natural language understanding.